Networks contain a collection of computing systems (e.g., clients and servers) that are interconnected by transmission lines to enable the transfer of data between them. A network typically includes multiple access points (e.g., routers and servers) that may switch and/or route data between transmission lines to transfer data from a source to a destination. Data is typically transmitted in the form of packets that are made up of smaller data cells. A packet is a unit of data that is routed between a source and a destination on a packet-switched network. When a file (e.g., e-mail, graphics, etc.) is sent from one place to another on a network, the file is divided into such smaller packets making them more efficient for transmission. The individual packets for a given file may travel different routes throughout networks with each packet containing both data and transmission information associated with the routing of data. As such, a packet may be described as having a payload containing the data, and one or more headers that contain the routing information (e.g., a destination address).
When all the packets have arrived at a destination, they are reassembled into the original file at the receiving end. Such a packet switching scheme is an efficient way to handle transmission on a connectionless network. This is in contrast to a circuit switching scheme where a connection (e.g., a voice connection) requires the dedication of a particular path for the duration of the connection.
A router is a device (e.g., hardware, firmware, software) that determines the next network segment to which a packet should be forwarded towards its destination. A router may be positioned at points within a network or where one network meets another, referred to as a gateway. A router may create and maintain tables of the available routes and their conditions for use with other information to determine the best route for a given packet. Typically, a packet may travel through a number of network points having routers before arriving at its destination.
When a data packet arrives at the input of a router, several lookups may be performed to determine the subsequent handling of the packet, as illustrated in FIG. 1. The lookups may include, for examples, where to send the packet next (Next Hop), the quality of service requirement (QoS), the Ethernet port address, etc. Consider, for example, a packet arriving at Router-A. Router-A needs to determine whether the packet is destined for local servers connected directly to Router-A, or if the packet should go to the next router on a route (Router-B) to a destination. Additionally, Router-A may assign a priority based on the destination address (DA) and the source address (SA) of the packet.
The packet header may first be parsed or processed to get the values from different fields (e.g., SA, DA, protocol type, QoS, etc) in order to perform the various lookups. A packet classification lookup, for example, may be performed using SA, DA and other relevant fields in the packet header. The Next Hop lookup, for example, may also be performed to determine whether the packet is meant for local servers or for Router-B. If the packet is destined for Router-B, the packet is then put in a queue for Router-B. If the packet is destined for a local server (e.g., Server-1 or Server-2), then a media access control (MAC) lookup is performed to send the packet to the appropriate server. In the preceding example, three lookups are necessary for sending the packet on its way: Packet Classification, Next Hop, and MAC. However, often there are other lookups performed on the packet header.
Routers may use processors and content addressable memory (CAM) devices to perform the various lookups on packets. As opposed to a random access memory (RAM) device, in which information is accessed by specifying a particular memory location address, the data stored in a CAM is accessed by the contents of the data. More specifically, instead of using an address to access a particular memory location, a CAM uses a key that contains a portion of the desired contents of a particular memory cell in the memory device. The CAM can be instructed by a processor to compare the key, also referred to as a comparand (e.g., packet header data) with data stored in its associative memory array, as illustrated in FIG. 2. The CAM simultaneously examines all of its entries and selects the stored data that matches the key.
When the entire CAM device, or blocks thereof, is searched simultaneously for a match of the stored data with the key/comparand, the CAM device indicates the existence of a match by asserting a match flag. Multiple matches may also be indicated by asserting a multiple match flag. The CAM device typically includes a priority encoder to translate the matched location into a match address or CAM index. The priority encoder may also sort out which matching memory location has the top priority if there is more than one matching entry.
Data may be represented in the form of strings of binary digits (“bits”) having a low (“0”) logic state and a high (“1”) logic state. Different types of CAMs may be used with different data formats. A binary CAM is designed to operate with “0” and “1” states, while a ternary CAM is designed to operate with “0”, “1”, and “don't care” states. The bits may be organized into groups such as a word (e.g., 64 or 72 bits wide) and stored in different segments of a CAM. The keys used for different data fields may have different word sizes, for example, the key for a Classification lookup may be 128 bits wide and the key for a Next Hop lookup may be 32 bits wide.
A router may include multiple CAMs, with each CAM having a different table or, alternatively, a single CAM having multiple block arrays for each of the different tables, for performing the different lookups. For example, a router may include a 32 bit wide Next Hop CAM, a 128 bit Classification CAM, and a 48 bit MAC CAM.
Each of the multiple CAMs, or CAM block arrays, are typically connected to common buses that are used to communicate the various search keys, indices, and other input and output data with each of the CAMs, or CAM block arrays. Thus, lookups are typically performed sequentially before a packet is processed (e.g., routed to the next destination or classified). Because the buses are shared with so many input and output functions of all the CAMs or CAM block arrays, many clock cycles are required to multiplex data on the bus. This generally limits the search rate and overall throughput of conventional CAM devices.
In some prior multiple block CAM devices, all of the block arrays typically participate in a given lookup. This can cause an undesirable amount of power to be drawn during the lookup. Other prior multiple block CAM devices use class codes and search codes to perform searches of different types on one or more of the array blocks. For example, different lookup tables may be formed spanning one or more of the array blocks. The array blocks associated with each lookup table are given a unique class code that identifies information stored in the table such as table configuration (i.e., width and depth) and type of data stored in the table (e.g., IP, MPLS, MAC lookup, etc.). A search code is typically provided with the search key in order to identify a particular table to be searched that has an associated class code matching the search code. However, the lookups in such prior CAM devices are performed using only a single search code at any given time. In other words, a search code is provided to the CAM device and only a table having a class code that matches the search code is searched. Therefore, lookups in tables having different class codes, based on different search codes, are performed sequentially before a packet is processed, thereby increasing device throughput.
As the number of ports, segments, or devices that are supported by routers increase and as the number of lookups increase, conventional CAM devices and architectures can undesirably limit the system's overall throughput and power consumption.
Some CAM devices store data in a preordered or prioritized manner such that higher priority data may be stored in lower logical addresses of the CAM array than lower priority data. Particular route data has a higher priority than other route data when such route data is to be selected over the other route data even though both route data may match a search key. The prioritizing of route data is typically performed by table management hardware and/or software that adds overhead to the router. If the table is not prioritized correctly, then an incorrect route may be selected for an incoming packet. When data stored in a CAM array is changed by adding new route data that has a higher (or equal) priority than data already stored in the CAM array, the table management hardware and software needs to reprioritize or reorder all or part of the CAM array. This is typically accomplished by reloading the CAM array with a new prioritized group of data. This can add significant overhead to the router (e.g., delay and additional hardware and software) to change a single route data stored in the CAM array.